package com.javabasic.algorithm.leetcode;

/**
 * @Author xiongmin
 * @Description //TODO
 * @Date 2020/2/4 15:07
 * @Version 1.0
 **/
public class UniquePathsII {

    /**
     * 动态规划解法
     * @param obstacleGrid
     * @return
     */
    public int uniquePathsWithObstacles2(int[][] obstacleGrid) {

        lenx = obstacleGrid.length;
        leny = obstacleGrid[0].length;
        int[][] dp = new int[lenx + 1][leny + 1];
        if (obstacleGrid[0][0] == 1 || obstacleGrid[lenx - 1][leny - 1] == 1) {
            return 0;
        }
        System.out.println(lenx + " " + leny);
        dp[1][1] = 1;
        for (int i = 1; i <= lenx; i++) {
            for (int j = 1; j <= leny; j++) {
                if (obstacleGrid[i][j] == 1) {
                    dp[i][j] = 0;
                } else {
                    dp[i][j] += dp[i][j - 1] + dp[i - 1][j];
                }
            }
        }
        return dp[lenx][leny];
    }

    int result = 0;
    int leny, lenx;

    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        lenx = obstacleGrid.length;
        leny = obstacleGrid[0].length;
        getResult(0, 0, obstacleGrid);
        return result;
    }

    /**
     * 递归解法--超时
     *
     * @param x
     * @param y
     * @param obstacleGrid
     */
    private void getResult(int x, int y, int[][] obstacleGrid) {
        if (x == lenx - 1 && y == leny - 1) {
            result++;
            return;
        }
        if (x >= lenx || y >= leny || obstacleGrid[x][y] == 1) {
            return;
        }
        getResult(x, y + 1, obstacleGrid);
        getResult(x + 1, y, obstacleGrid);
    }
}
